package logica.acciones;
import java.util.Collections;
import java.util.Vector;

public class BusquedaRecorrido {
	int worldHeight = 25;
	int worldWidth = 25;
	int worldSize;
	int walkableCell;
	int[][] map;
	
	private class Node{
		
		Node parent;
		int value;
		int x;
		int y;
		double f;
		double g;
		
		// Node class, returns a new object with Node properties
		// Used in the calculatePath function to store route costs, etc.
		public Node(Node parent, Coordenada point){
			this.parent = parent;
			this.value = point.getX() + (point.getY() * worldWidth);
			this.x = point.getX();
			this.y = point.getY();
			this.f = 0;
			this.g = 0;
		}		
	}
	
	public BusquedaRecorrido(int[][] map, int walkableCell){		
		this.map = map;
		this.worldWidth = map.length;
		this.worldHeight = map[0].length;
		this.walkableCell = walkableCell;
		this.worldSize = this.worldWidth * this.worldHeight;
	}	
	
	/*
	private double DiagonalDistance(Coordenada actual, Coordenada destino)
	{	// diagonal movement - assumes diag dist is 1, same as cardinals
		return Math.max(Math.abs(actual.getX() - destino.getX()), Math.abs(actual.getY() - destino.getY()));
	}
	*/

	private double EuclideanDistance(Coordenada actual, Coordenada destino)
	{	// diagonals are considered a little farther than cardinal directions
		// diagonal movement using Euclide (AC = sqrt(AB^2 + BC^2))
		// where AB = x2 - x1 and BC = y2 - y1 and AC will be [x3, y3]		
		return Math.sqrt(Math.pow(actual.getX() - destino.getX(), 2) + Math.pow(actual.getY() - destino.getY(), 2));
	}
	
	// Returns every available N,NW,NE,S,SW,SE,E,W
	// cell that is empty.
	private Vector<Coordenada> Neighbours(Coordenada punto)
	{
		int x = punto.getX();
		int y = punto.getY();
		
		int	N = y - 1,
		S = y + 1,
		E = x + 1,
		W = x - 1;		
		
		boolean
		myN = N > -1 && canWalkHere(new Coordenada(x, N)),
		myS = S < worldHeight && canWalkHere(new Coordenada(x, S)),
		myE = E < worldWidth && canWalkHere(new Coordenada(E, y)),
		myW = W > -1 && canWalkHere(new Coordenada(W, y));
		
		Vector<Coordenada> result = new Vector<Coordenada>();

		if(myN)
			result.add(new Coordenada(x, N));
		if(myE)
			result.add(new Coordenada(E, y));
		if(myS)
			result.add(new Coordenada(x, S));
		if(myW)
			result.add(new Coordenada(W, y));
		
		DiagonalNeighbours(myN, myS, myE, myW, N, S, E, W, result);
		
		return result;
	}
	
	// returns every available North East, South East,
	// South West or North West cell - no squeezing through
	// "cracks" between two diagonals
	private void DiagonalNeighbours(boolean myN, boolean myS, boolean myE, boolean myW, int N, int S, int E, int W, Vector<Coordenada> result)
	{
		if(myN)
		{		
			if(myE && canWalkHere(new Coordenada(E, N)))
				result.add(new Coordenada(E, N));
			if(myW && canWalkHere(new Coordenada(W, N)))
				result.add(new Coordenada(W, N));
		}
		if(myS)
		{
			if(myE && canWalkHere(new Coordenada(E, S)))
				result.add(new Coordenada(E, S));
			if(myW && canWalkHere(new Coordenada(W, S)))
				result.add(new Coordenada(W, S));
		}
	}	
	
	private boolean canWalkHere(Coordenada coord)
	{/*
		return ((world[x] != null) &&
			(world[x][y] != null) &&
			(world[x][y] <= maxWalkableTileNum));
			*/
		return map[coord.getY()][coord.getX()] == walkableCell;
	}

	public Vector<Coordenada> calculatePath(Coordenada pathStart, Coordenada pathEnd)
	{
		// create Nodes from the Start and End x,y coordinates
		Node mypathStart = new Node(null, pathStart);
		Node mypathEnd = new Node(null, pathEnd);
		// create an array that will contain all world cells
		boolean[] AStar = new boolean[worldSize];
		
		// list of currently open Nodes
		Vector<Node> Open = new Vector<Node>();
		Open.add(mypathStart);
		
		// list of closed Nodes
		Vector<Node> Closed = new Vector<Node>();
		
		// list of the final output array
		Vector<Coordenada> result = new Vector<Coordenada>();
		// reference to a Node (that is nearby)
		Vector<Coordenada> myNeighbours;
		// reference to a Node (that we are considering now)
		Node myNode;
		// reference to a Node (that starts a path in question)
		Node myPath;
		// temp integer variables used in the calculations
		int length,  min, i, j;
		double max;
		
		length = Open.size();
		// iterate through the open list until none are left
		while(length > 0)
		{
			max = worldSize;
			min = -1;
			for(i = 0; i < length; i++)
			{
				if(Open.get(i).f < max)
				{
					max = Open.get(i).f;
					min = i;
				}
			}
			// grab the next node and remove it from Open array
			myNode = Open.get(min);
			myNode = Open.remove(min);
			//myNode = Open.splice(min, 1)[0];
			
			// is it the destination node?
			if(myNode.value == mypathEnd.value)
			{
				Closed.add(myNode);
				myPath = Closed.get(Closed.size() - 1);
				do
				{
					result.add(new Coordenada(myPath.x, myPath.y));
					myPath = myPath.parent;
				}
				while (myPath != null);
				// clear the working arrays
				//AStar = Closed = Open = [];
				// we want to return start to finish
				Collections.reverse(result);
			}
			else // not the destination
			{
				// find which nearby nodes are walkable
				myNeighbours = Neighbours(new Coordenada(myNode.x, myNode.y));
				// test each one that hasn't been tried already
				for(i = 0, j = myNeighbours.size(); i < j; i++)
				{
					myPath = new Node(myNode, myNeighbours.get(i));
					if (!AStar[myPath.value])
					{
						// estimated cost of this particular route so far
						myPath.g = myNode.g + EuclideanDistance(myNeighbours.get(i), new Coordenada(myNode.x, myNode.y));
						// estimated cost of entire guessed route to the destination
						myPath.f = myPath.g + EuclideanDistance(myNeighbours.get(i), new Coordenada(mypathEnd.x,mypathEnd.y));
						// remember this new path for testing above
						Open.add(myPath);
						// mark this node in the world graph as visited
						AStar[myPath.value] = true;
					}
				}
				// remember this route as having no more untested options
				Closed.add(myNode);
			}
			length = Open.size();
		} // keep iterating until the Open list is empty
		return result;
	}
}
